import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-02-08
 * Time: 21:34
 */
class Solution {
    // dfs + 剪枝
    int[] arr;
    int length;
    List<List<Integer>> lists=new ArrayList<>();
    List<Integer> list=new ArrayList<>();
    public void dfs(int index,int k){
        // 剪枝一:
        // 因为这里是已进入函数就判断长度
        // 所以如果长度 ==k 满足条件 加入后直接停止就行
        if(list.size()==k){
            lists.add(new ArrayList<>(list));
            return ;
        }
        // 剪枝二:
        // 这里不用再判断 下标是否越界的问题
        // 因为 后面的 判断当前所有元素是否能凑够 k　个, 这里面已经 隐含了这个条件
        if(list.size()>k||list.size()+ (length-index+1) <k){
            return;
        }
        // 考虑当前元素
        list.add(arr[index]);
        dfs(index+1, k);
        // 不考虑当前元素
        list.remove(list.size()-1);
        dfs(index+1, k);
    }
    public List<List<Integer>> combine(int n, int k) {
        this.arr=new int[n+1];
        this.length=n;
        for(int i=1;i<=n;i++){
            arr[i]=i;
        }
        dfs(1,k);
        return lists;
    }
}
